#ifndef BLOOMFILTER
#define BLOOMFILTER

#include <cmath>
#include "bitmap.h"

namespace bitset
{
    struct BKDRHash
    {
        size_t operator()(const std::string &str) const
        {
            size_t hash = 0;
            for (char ch : str)
            {
                hash = hash * 131 + static_cast<size_t>(ch);
            }
            return hash;
        }
    };

    struct DJBHash
    {
        size_t operator()(const std::string &str) const
        {
            if (str.empty())
                return 0;
            size_t hash = 5381;
            for (char ch : str)
            {
                hash += (hash << 5) + static_cast<size_t>(ch);
            }
            return hash;
        }
    };

    struct PJWHash
    {
        size_t operator()(const std::string &str) const
        {
            static const size_t TotalBits = sizeof(size_t) * 8;
            static const size_t ThreeQuarters = (TotalBits * 3) / 4;
            static const size_t OneEighth = TotalBits / 8;
            static const size_t HighBits = ((size_t)-1) << (TotalBits - OneEighth);

            size_t hash = 0;
            size_t magic = 0;
            for (char ch : str)
            {
                hash = (hash << OneEighth) + static_cast<size_t>(ch);
                if ((magic = hash & HighBits) != 0)
                {
                    hash = ((hash ^ (magic >> ThreeQuarters)) & (~HighBits));
                }
            }
            return hash;
        }
    };

    template <size_t N,
              size_t X = 5,
              typename K = std::string,
              typename HashFunc1 = BKDRHash,
              typename HashFunc2 = DJBHash,
              typename HashFunc3 = PJWHash>
    class BloomFilter
    {
    public:
        void set(const K &key)
        {
            size_t hash1 = HashFunc1()(key) % M;
            size_t hash2 = HashFunc2()(key) % M;
            size_t hash3 = HashFunc3()(key) % M;

            _bits.set(hash1);
            _bits.set(hash2);
            _bits.set(hash3);
        }

        bool check(const K &key)
        {
            size_t hash1 = HashFunc1()(key) % M;
            if (!(_bits.check(hash1)))
                return false;

            size_t hash2 = HashFunc2()(key) % M;
            if (!(_bits.check(hash2)))
                return false;

            size_t hash3 = HashFunc3()(key) % M;
            if (!(_bits.check(hash3)))
                return false;

            return true;
        }

        // 误判率
        double getFalseProbability()
        {
            double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);

            return p;
        }

        /**
         * 没有删除，因为布隆过滤器存在误判的可能，如果增加了删除的功能，可能会删除已经存在的值
         * 增加删除也可以，用一个引用计数的功能，管理每个位置，但还是不建议，因为布隆过滤器存在误判
         */
    private:
        static const size_t M = N * X;
        bitset::bitmapofVector<M> _bits;
    };
}
#endif